#include "list.h"

// correto e seguro
No* criarNo()
{
	No *N = (No*) malloc(sizeof(No));
	N->valor = N->prox = N->anterior = NULL;
	return(N);
}

/* CORRETO E SEGURO!!! (livre de memory leaks) */
void liberarNo(No* N)
{
	if(N != NULL) free(N);
}

// correto e seguro
Lista* criarLista()
{
	Lista *L = (Lista*) malloc(sizeof(Lista));
	L->inicio = criarNo();
	L->fim = criarNo();
	
	L->inicio->prox = L->fim;
	L->fim->anterior = L->inicio;
	
	L->size = 0;
	return(L);
}

/* CORRETO E SEGURO!!! (livre de memory leaks) */
void liberarLista(Lista *L)
{
	if(L != NULL)
	{
		while(!taVazia(L))
			removerInicio(L);
		
		liberarNo(L->inicio);
		liberarNo(L->fim);
		
		free(L);
		L = NULL;
	}
}

// o 'const' usado abaixo serve para que nao
// corramos o risco de alterar nada do L original
int taVazia(const Lista *L)
{
	// ou if (L->size == 0) , da no mesmo
	if(L->inicio->prox == L->fim)
		return 1;
	else
		return 0;
}

void inserirInicio(Lista *L, tipo_lista dado)
{
	if( taVazia(L) )
	{
		No *novo = criarNo();
		novo->valor = dado;
		
		L->inicio->prox = novo;
		L->fim->anterior = novo;
		
		novo->prox = L->fim;
		novo->anterior = L->inicio;
		
		L->size++;
	}
	else
	{
		No *novo = criarNo();
		novo->valor = dado;
		
		No *aux = L->inicio->prox;
		
		aux->anterior = novo;
		novo->prox = aux;
		
		L->inicio->prox = novo;
		novo->anterior = L->inicio;
		
		L->size++;
	}
}

void inserirFim(Lista *L, tipo_lista dado)
{
	if( taVazia(L) )
		inserirInicio(L, dado);
	else
	{
		No *novo = criarNo();
		novo->valor = dado;
		
		No *aux = L->fim->anterior;
		
		aux->prox = novo;
		novo->anterior = aux;
		
		novo->prox = L->fim;
		L->fim->anterior = novo;
		
		L->size++;
	}
}

void inserirOrdenado(Lista *L, tipo_lista dado, int(*compara)(const void* a, const void* b) )
{
	if( taVazia(L) )
		inserirInicio(L, dado);
	else
	{
		No *aux;
		for(aux = L->inicio->prox; aux != L->fim; aux = aux->prox)
		{
			if(compara(aux->valor, dado) >= 0)
				break;
		}
		if( aux == L->fim )
			inserirFim(L, dado);
		else
		{
			No *novo = criarNo();
			novo->valor = dado;
			
			aux->anterior->prox = novo;
			novo->anterior = aux->anterior;
			
			novo->prox = aux;
			aux->anterior = novo;
			
			L->size++;
		}
	}
}

tipo_lista buscar(const Lista* L, const tipo_lista elem, int(*compara)(const void* a, const void* b) )
{
	if( taVazia(L) )
		return NULL;
	else {
		No *aux;
		for(aux = L->inicio->prox; aux != L->fim; aux = aux->prox)
		{
			if( compara( aux->valor, elem ) == 0)
				return( aux );
		}
		return NULL;
	}
}

No* removerNo(No* no)
{
	if(no) {
		No* anterior = no->anterior;
		No* proximo = no->prox;
		anterior->prox = proximo;
		proximo->anterior = anterior;

		liberarNo(no);

		return anterior;
	}
	return NULL;
}

No* proximoNo(No* no) {
	if(no)
		return no->prox;

	return NULL;
}

int ultimoNo(const Lista* L, No* no) {
	if(L == NULL || no == NULL)
		return -1;

	return(no == L->fim);
}

int removerInicio(Lista *L)
{
	if( taVazia(L) ) {
		return(0);
	}
	else {
		No *saida = L->inicio->prox;
		
		saida->prox->anterior = L->inicio;
		L->inicio->prox = saida->prox;
		
		liberarNo(saida);
		L->size--;
		return(1);
	}
}

tipo_lista primeiro(Lista* L)
{

	return L->inicio->prox->valor;
}

No* primeiroNo(const Lista* L)
{
	if(L)
		return L->inicio->prox;
	else
		return NULL;
}

int removerFim(Lista *L)
{
	if( taVazia(L) ) {
		return(0);
	}
	else {
		No *saida = L->fim->anterior;
		
		saida->anterior->prox = L->fim;
		L->fim->anterior = saida->anterior;
		
		liberarNo(saida);
		L->size--;
		return(1);
	}
}

